703D - Mishka and Interesting sum - CodeForces Solution

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000010;
int a[N],pre[N],n,ans[N],b[N];
map<int,int> sq;
std::vector<pair<int,int>> e[N];
template<class T>
struct BIT {
    T c[N];
    int size;
    void resize(int s) { size = s;}
    T query(int x) { // 1 ... x
        if(x>size){
            return 0;
        }
        T s = 0;
        for (; x; x -= x & (-x)) {
            s = (c[x]^s);
        }
        return s;
    }

    void modify(int x, T s) { // a[x] += s
        if(x==0){
            return;
        }
        for (; x <= size; x += x & (-x)) {
            c[x] = (c[x]^s);
        }
    }
};
BIT<int> c;
void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
        b[i]^=b[i-1];
        pre[i]=sq[a[i]];
        sq[a[i]]=i;
    }
    c.resize(n+8);
    int q;
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        e[r].push_back({l,i});
        ans[i]=(b[r]^b[l-1]);
    }
    for(int i=1;i<=n;i++){
        if(pre[i]==0){
            c.modify(i,a[i]);
        }else{
            c.modify(pre[i],a[i]);
            c.modify(i,a[i]);
        }
        for(auto [x,y]:e[i]){
            ans[y]^=(c.query(i)^c.query(x-1));
        }
    }
    for(int i=1;i<=q;i++){
        printf("%d\n",ans[i]);
    }
}


int main() 
{
    std::ios::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);
    int _=1;
    while(_--){
        solve();
    }
    return 0;
}